Computer graphic systems and real time simulation visual systems construct images of visual scenes. Each image is a rectangular array of pixels, and each pixel represents a small, typically square, region to which a single color or shade of gray is assigned.
Approximating a scene by an array of pixels can result in artifacts that degrade the quality of the resultant image. An important class of these artifacts is called "aliasing effects" , and these effects are commonly known in the computer graphics industry. Aliasing effects result from selecting the wrong color to approximate a pixel due to incorrect sampling of the underlying image.
For example, a pixel area that corresponds to a region that is half white and half black should be approximated as being uniformly gray. Aliasing results if the pixel is colored entirely black or entirely white due to a failure to correctly sample and combine the underlying black and white regions.
Anti-aliasing is the process of reducing the undesirable effects of aliasing. Most methods rely upon "point sampling" , which is the class of methods that involve computing discrete values of both color and intensity within each pixel of an image and, then, combining the samples into values to be displayed for each pixel. The quality of point sampling depends critically upon how the sample points are positioned within the pixel.
A text entitled Principles of Interactive Computer Graphics by Newman/Sproull (McGraw-Hill, 1979, 2nd Edition) provides an overview of the techniques. An article entitled Spectrally Optimal Sampling for Distribution Ray Tracing by Don P. Mitchell (Proceedings of SIGGRAPH '91 in Computer Graphics, 25, 4 of Jul. 1991, ACM SIGGRAPH, New York, 1991, pp. 157-162) provides a more specialized treatment.
Sample point positions are used for occlusion masks (or coverage masks). An "occlusion mask" is a means of summarizing which sample points in a pixel have been covered by one or more graphics primitives while rendering a computer graphics image.
Occlusion masks are used in several different ways in computer graphics systems, but all of the uses relate to improving the quality of the image by keeping track of pixel coverage at a sub-pixel level. Some computer graphics systems write objects into a frame buffer in reverse order of occlusion, i.e., the nearest objects are written first.
Occlusion masks are used also with z-buffering systems. An occlusion mask for a computer graphics system is a bit-map, wherein each bit represents each point in an array of points constrained within a rectangular boundary.
Because point sampling is used for both anti-aliasing and sub-pixel occlusion in a great variety of computer graphics systems, and because the image quality depends directly on the positions of the sample points, the method of point sampling is very important. The problem of finding a good method for selecting point samples is deceptively difficult.
One approach is to put the sample points in a rectangular array. Another approach is to place them at random in the pixel. Both of these approaches have strong drawbacks that degrade image quality.
Arranging sample points in a grid allows a small motion of a polygon between images in a sequence to cover an entire row, column, or diagonal of sample points. Thus, for example, if 16 points are placed in a 4 .times.4 array, for many cases the result will only be as good as if four points were used.
The array is effective in covering small polygons. However, this advantage is strongly outweighed by the disadvantage of polygon edges covering a whole line of point samples at one time.
Placing points at random (or when a computer does the placement by a repeatable but apparently random process, pseudo-randomly), allows some placements to be quite poor, because points can be placed close together. A variation of random placement is to protect each sample with a region, a so-called Poisson Disk, within which no other point can be placed.
The Poisson Disk method does not work if the disks are too large, because placement becomes impossible. However, if the disks are small enough to ensure placement, the disadvantages of random placement reappear.
Another variation of random placement is a method by Cook et al. (U.S. Pat. No. 5,025,400) which is to use sample points that are pseudo-randomly distributed, and the best placement is selected by reference to the spectrum of the sampling frequency. A limitation of this method is that it does not guarantee optimal sampling in the horizontal and vertical directions.
Images typically have many horizontal and vertical edges corresponding to edges of buildings and other man-made structures, the horizon, and other features. Failure to treat horizontal and vertical edges well is a limitation of sampling with a grid and with many methods.
Yet another class of methods, known as rook placement, does guarantee optimal horizontal and vertical sampling. This method is named by analogy to rooks on a chessboard. Eight rooks can be placed on a chessboard so that no two are in the same row or column.
Similarly, "N" sample points can be placed at points within one N .times.N grid within a pixel so that no two are in the same row and column. For example, one rook placement is to put all N samples on the diagonal of the N .times.N grid.
Diagonal placement, like all rook placements, ensures N equally spaced horizontal and vertical samples. However, diagonal placement also is very poor placement for most other cases; polygon edges that happen to fall nearly parallel to the sampled diagonal receive little or no anti-aliasing.
While the rook placement concept has long been known to have great potential as a point sampling method, the problem of selecting specific rook placements has remained unsolved to this day. An overview of the problem is given by Mitchell in the 1991 SIGGRAPH paper, supra. Mitchell cites earlier work by Cook and by Shirley leading up to sampling arrangements in which a pixel is subdivided into an N .times.N mesh, with N points placed in block centers so that no two are in the same row or column.
Mitchell goes on to say, "There seems to remain an important piece of unfinished business. We really do not know much about what constitutes a good sampling design versus a bad one."